package work.string;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Problem76 {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> tmap = new HashMap<>();
        for (char c : t.toCharArray()) {
            Integer orDefault = tmap.getOrDefault(c, 0);
            tmap.put(c, ++orDefault);
        }
        HashMap<Character, Integer> smap = new HashMap<>();
        int i = 0;
        int n = s.length();
        int leftMin = -1;
        int rightMin = n;
        for (int j = 0; j < n; j++) {
            Integer orDefault = smap.getOrDefault(s.charAt(j), 0);
            orDefault++;
            smap.put(s.charAt(j), orDefault);
            while (check(smap, tmap)) {
                if (j - i < rightMin - leftMin) {
                    rightMin = j;
                    leftMin = i;
                }
                Integer num = smap.get(s.charAt(i));
                smap.put(s.charAt(i),--num);
                i++;
            }
        }
        return  leftMin < 0 ? "" : s.substring(leftMin, rightMin + 1);
    }


    private boolean check(HashMap<Character, Integer> smap, HashMap<Character, Integer> tmap) {
        for (char c : tmap.keySet()) {
            Integer scount = smap.get(c);
            Integer tcount = tmap.get(c);
            if (scount == null) return false;
            if (scount < tcount) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Problem76 problem76 = new Problem76();
        problem76.minWindow("ADOBECODEBANC","ABC");
    }
}
